package com.mjf.stack;

import java.util.Scanner;

/**
 * 使用单链表模拟栈
 */
public class LinkedListStackDemo {

    public static void main(String[] args) {

        // 测试LinkedListStack是否正确
        LinkedListStack stack = new LinkedListStack(5);
        String key = "";
        boolean loop = true;    // 控制是否退出菜单
        Scanner scanner = new Scanner(System.in);

        while (loop) {
            System.out.println("================================");
            System.out.println("show：显示栈");
            System.out.println("exit：退出程序");
            System.out.println("push：添加数据到栈(入栈)");
            System.out.println("pop：从栈取出数据(出栈)");
            System.out.println();

            key = scanner.next(); // 接收用户输入
            switch (key) {
                case "show":
                    stack.list();
                    break;

                case "push":
                    System.out.println("输入一个数：");
                    String value = scanner.next();
                    stack.push(value);
                    break;

                case "pop":
                    try {
                        String result = stack.pop();
                        System.out.printf("取出的数据是%s\n", result);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case "exit":
                    scanner.close();
                    loop = false;
                    break;

                default:
                    break;
            }
        }

    }

}


/**
 * 使用单链表模拟栈
 * <p>
 * 栈顶：头节点下一个节点
 */
class LinkedListStack {

    private final int maxSize;    // 栈的大小
    private final StackNode first = new StackNode("");    // 定义头节点,不存放数据

    public LinkedListStack(int maxSize) {
        this.maxSize = maxSize;
    }

    // 栈满
    public boolean isFull() {
        int count = 0;
        StackNode temp = first.next;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count == maxSize;
    }

    // 栈空
    public boolean isEmpty() {
        return first.next == null;
    }

    // 入栈
    public void push(String value) {
        // 先判断是否栈满
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        StackNode node = new StackNode(value);
        StackNode cur = first;   // 定义辅助节点

        if (isEmpty()) {     // 链表为空时直接加入
            cur.next = node;
            return;
        }

        node.next = cur.next;
        first.next = node;
    }

    // 出栈:将栈顶的数据返回
    public String pop() {
        // 先判断是否栈空
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        StackNode top = first.next;     // 表示栈顶数据
        first.next = top.next;  // 栈顶数据出栈

        return top.value;
    }

    // 遍历栈，遍历时需要从栈顶开始显示数据
    public void list() {
        if (isEmpty()) {
            System.out.println("栈空，没有数据");
        }
        StackNode top = first.next; // 表示栈顶

        while (top != null) {
            System.out.printf("stack:%s\n", top.value);
            top = top.next;
        }
    }

}

// 定义栈节点
class StackNode {
    public String value; // 表示节点数据
    public StackNode next;  // 表示链表的下一个节点

    public StackNode(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "StackNode{" +
                "value=" + value +
                '}';
    }
}